1. Field of the Invention
The present invention generally relates to the field of cryptography, particularly to cryptographic methods and devices and, even more particularly, to methods for preventing security attacks to cryptosystems based on information leakage.
2. Description of the Related Art
The past approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not to be considered prior art to the claims in this application merely due to the presence of these approaches in this background section. In modern data communication systems, a wide use of cryptographic techniques providing confidentiality and authenticity of information was enabled by the invention (by W. Diffie and M. Hellman in 1976) of so-called “public-key cryptosystems”, which provide efficient solutions to the inherent secret-key management problem.
In particular, public-key cryptosystems are mostly used for Diffie-Hellman key exchange, for digital signatures, and for encrypting secret session keys to be used in secret-key cryptosystems. For example, they are used in the Internet protocols including Secure Socket Layer (SSL), Internet Protocol Security (IPSec), and Pretty Good Privacy (PGP).
Elliptic Curve Cryptosystems (ECCs), proposed independently by V. S. Miller in 1985 and N. Koblitz in 1987, are evolving as an efficient alternative to classical public-key cryptosystems, such as Diffie-Hellman key exchange based on finite field multiplicative groups and RSA, invented by R. L. Rivest, A. Shamir, and L. Adleman in 1978, by offering the same security level for much smaller key sizes, thus allowing for more efficient implementations both in hardware and software.
Typical ECCs include cryptographic protocols Elliptic Curve Diffie-Hellman (ECDH), used for secret key exchange, and Elliptic Curve Digital Signature Algorithm (ECDSA), adopted as international standard ANSI X9.62, used for digital signatures. The protocols are also covered by the IEEE 1363 series of standards.
ECCs are based on mathematical entities called the elliptic curve groups. An elliptic curve group is defined as an Elliptic Curve (EC), which is a set of solutions, called “the points”, to an elliptic curve equation, together with an appropriately defined operation among the points on the curve.
The basic two types of ECs are defined over the fields containing a prime number of elements and over the fields with the number of elements being an integer power of 2. The former are also called the prime fields or integer fields or fields of a prime characteristic, their elements are integers, and operations of addition and multiplication are defined modulo a prime number. The latter are also called binary polynomial fields or fields of characteristic 2, their elements are binary polynomials, and operations of addition and multiplication are defined as addition and multiplication of polynomials modulo an irreducible polynomial, respectively.
A prime field, Fp, is a finite field with p elements, where p is a prime number. It is composed of a set of integers {0, 1, 2, . . . , p−1}, together with the operations of addition and multiplication defined as addition and multiplication of integers modulo p, respectively.
According to the Weierstrass equation, an elliptic curve:E(Fp):y2=x3+ax+b over Fp, p>3, specified by two parameters a,bεFp satisfying the condition 4a3+27b2≠0 mod p, is defined as the set of points P=(x,y), x,yεFp, being the solutions to the equation:y2=x3+ax+b, together with a special, neutral point O, called the point at infinity. The couple (x,y) represents the x-coordinate and the y-coordinate of a generic point P on an elliptic curve.
An elliptic curve forms a group with respect to the operation, called the addition, which is defined as follows.                Neutral point: P+O=O+P=P for all P=(x,y)εE(Fp).        Negative point: If P=(x,y)εE(Fp), then (x,y)+(x,−y)=O, and (x,−y)εE(Fp) is denoted as −P and is called the negative of P.        Addition of points: Let P=(x1,y1)εE(Fp) and Q=(x2,y2)εE(Fp), where P≠±Q. Then P+Q=(x3,y3), where:        
            x      3        =                  λ        2            -              x        1            -              x        2              ,          ⁢            y      3        =                  λ        ⁡                  (                                    x              1                        -                          x              3                                )                    -              y        1              ,          ⁢      λ    =                                        y            2                    -                      y            1                                                x            2                    -                      x            1                              .                      Doubling of a point: Let P=(x1,y1)εE(Fp), where P≠O. Then P+P=2P=(x3,y3), where:        
            x      3        =                  λ        2            -              2        ⁢                  x          1                      ,          ⁢            y      3        =                  λ        ⁡                  (                                    x              1                        -                          x              3                                )                    -              y        1              ,          ⁢      λ    =                                        3            ⁢                          x              1              2                                +          a                          2          ⁢                      y            1                              .      
Consequently, the addition of points can be performed as a sequence of multiplications, squaring operations, subtractions, and inversions over Fp, whereas the doubling of a point can be performed as a sequence of multiplications, squaring operations, subtractions, additions, doublings, and inversions over Fp.
In order to avoid the burden of computing the inversion, which is typically much more complex than computing the other operations in Fp, an elliptic curve point can be represented by the so-called “projective coordinates” instead of the classical, “affine coordinates”.
For a point P given in affine coordinates as P=(xa,ya), the representation in projective coordinates is given as P=(xp,yp, zp), where (xp,yp, zp)=(λ·xa, λ·ya, λ) and λ≠0 is arbitrary. The projective coordinates are thus not unique. The conversions between the coordinates are performed by the following formulas:
                    (                              x            a                    ,                      y            a                          )            →              (                              x            a                    ,                      y            a                    ,          1                )              =          (                        x          p                ,                  y          p                ,                  z          p                    )        ,          ⁢                    (                              x            p                    ,                      y            p                    ,                      z            p                          )            →              (                                            x              p                                      z              p                                ,                                    y              p                                      z              p                                ,                                    z              p                                      z              p                                      )              =                  (                              x            a                    ,                      y            a                    ,          1                )            →                        (                                    x              a                        ,                          y              a                                )                .            
The projective coordinates are convenient to represent the neutral point by zp=0, for example, as (1, 1, 0).
It is known that the point addition and doubling in projective coordinates can be performed by using the following formulas (as described for example in K. Koyama and Y. Tsuruoka, “Speeding up elliptic cryptosystems by using a signed binary window method,” Advances in Cryptology—Crypto '92, Lecture Notes in Computer Science, vol. 740, pp. 345-357, 1993).                Addition of P=(x1,y1, z1) and Q=(x2,y2, z2) into P+Q=(x3,y3, z3): u1=y2z1−y1, z2, u2=x2z1−x1z2, u3=x2z1+x1z2, u4=u12z1z2−u22u3, x3=u2u4, y3=u1(u22x1z2−u4)−u23y1z2, z3=u23z1z2.        Doubling of P=(x1,y1, z1) into 2P=(x3,y3, z3): u1=y1z1, u2=3x12+az12, u3=y1u1, u4=x1u3, u5=u22−8u4 x3=2u1u5, y3=u2(4u4−u5)−8u32, z3=8u13.        
Differently from the point addition and doubling in affine coordinates, the formulas in projective coordinates do not include the inversion, so this costly operation is avoided, but the number of multiplications is increased.
Accordingly, to perform a sequence of point additions and/or doublings in projective coordinates, the inversions need to be computed only at the end, when the projective coordinates are converted back to the affine coordinates.
In particular, it is known, as for example described in U.S. Pat. No. 6,714,648 B2, that the inversion in any finite field can be implemented as an exponentiation, in view of the fact that in a field with q elements it is true that x−1=xq−2.
There are also other known coordinate systems for achieving the same objective, such as the so-called Jacobian and Chudnovsky coordinates, or combinations thereof Typically, the number of multiplications for the point doubling can thus be reduced, at the expense of further increasing the number of multiplications for the point addition.
The main operation over elliptic curve groups that is required for cryptosystems such as ECDH or ECDSA is a repeated addition of a generic point P with itself k−1 times, P+ . . . +P, an operation called the “scalar multiplication” of a base point P by a scalar k and is denoted as kP, where k is a positive integer. In practical applications, k is a secret and very big number, typically, several hundred bits long. The base point P can be selected according to the criteria specified in the cryptosystems ECDH and ECDSA.
The scalar multiplication can be computed efficiently by using an algorithm called “double-and-add”, in the left-to-right (i.e., going from the most significant bit of k downwards) or right-to-left (from the least significant bit of k upwards) manner, where
  k  =                    (                              k                          t              -              1                                ,                      k                          t              -              2                                ,          …          ⁢                                          ,                      k            1                    ,                      k            0                          )            2        =                  ∑                  i          =          0                          t          -          1                    ⁢                          ⁢                        k          i                ⁢                              2            i                    .                    The algorithm consists of a series of point doublings and point additions, where the positions of point additions depend on the scalar k. More precisely, the algorithm consists of t iterations, each iteration consisting of a point doubling that is followed by a point addition only if the corresponding scalar bit is equal to 1.
It is known in the art that if a cryptographic algorithm, such as, for example an ECC, is implemented on a microelectronic device, e.g., an integrated circuit chip card, then even for tamper-resistant chips, where the underlying integrated circuit is protected by special physical measures, such as protective layers and various sensors and detectors, the sensitive information, dependent on the underlying secret or private key, being processed during the execution of the cryptographic algorithm may leak out through various side channels, for example, through measurements of the timing, power consumption, and electromagnetic radiation, as well as monitoring of signals by micro-probing. The objective of these “side-channel” attacks is to recover the secret key by using the information leaking out from said side channels.
In particular, the timing attacks were introduced by P. Kocher, in “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems”, Advances in Cryptology—Crypto '96, Lecture Notes in Computer Science, vol. 1109, pp. 104-113, 1996; the power analysis attacks were introduced by P. Kocher, J. Jaffe, and B. Jun, in “Differential power analysis,” Advances in Cryptology—Crypto '99, Lecture Notes in Computer Science, vol. 1666, pp. 388-397, 1999.
The two basic power analysis attacks are Simple Power Analysis (SPA) attacks and Differential Power Analysis (DPA) attacks. An SPA attack utilizes a single power consumption curve and tries to deduce information about the secret key from this curve, whereas a DPA attack utilizes a set of power consumption curves, guesses a part of the secret key, and then verifies if the guess is correct by a simple processing of the curves according to the corresponding guess. The timing attacks can utilize single or multiple measurements.
The timing and power analysis attacks do not require expensive resources, and most implementations, without specific countermeasures incorporated therein, are vulnerable to them. Therefore, there is a need to protect the sensitive data from side-channel attacks by appropriate changes in the cryptographic algorithm, of course, without changing the overall functionality of the algorithm.
A problem with a direct implementation of the double-and-add algorithm for performing the scalar multiplication is that the computations required for the point addition and the point doubling in general are different (for example, the two operations may differ in the total numbers of field multiplications and/or of squaring operations required). As a consequence, the timing, as well as the power consumption of a hardware device implementing the cryptographic algorithm significantly depend on the secret scalar k. Thus, the double-and-add algorithm is potentially vulnerable to the timing attack and SPA attack: by analyzing the timing and/or the power consumption curve it may be possible to identify the iterations where the point addition is effectively performed, that is, when the scalar bit is equal to 1, and thus reconstruct the secret scalar.
One known way of dealing with this problem is to modify the basic double-and-add algorithm by introducing a dummy point addition whenever the corresponding scalar bit is equal to 0, which results in the so-called “double-and-add-always” algorithm or, possibly, to perform other algorithms, as sequences of point doublings, additions, and subtractions, which are different from the double-and-add algorithm in that they have a more balanced timing and power consumption. Typically, the modified or new algorithms require a considerable increase of the total computation time needed.
A different approach aims at balancing the computations required for the point addition and point doubling themselves. For example, C. H. Gebotys and R. J. Gebotys, in “Secure elliptic curve implementations: An analysis of resistance to power-attacks in a DSP processor,” Cryptographic Hardware and Embedded Systems—CHES 2002, Lecture Notes in Computer Science, vol. 2523, pp. 114-128, 2002, suggest to work in the Jacobian coordinates and to represent the sequence of field operations required for the point addition as a sequence of operations required for the point doubling (with different operands) repeated twice, which makes it difficult to identify the iterations when the scalar bit is equal to 1. This was achieved for a specific case a=−3 mod p, by introducing some dummy elementary operations and by an appropriate reordering of the elementary operations.
Another method of a similar type, also dealing with the Jacobian coordinates, but in a general case when the parameter a can take any value, is proposed by B. Chevallier-Mames, M. Ciet, and M. Joye, in “Low-cost solutions for preventing simple side-channel analysis: Side-channel atomicity,” IEEE Transactions on Computers, vol. 53 (6), pp. 760-768, 2004. In this method, the point addition and point doubling are balanced by representing each of them as a sequence of elementary (atomic) blocks of operations, which themselves are assumed to be indistinguishable with respect to side-channel attacks. Each atomic block can be represented as the same sequence of field operations (one multiplication, two additions, and one negation) and some pointer update instructions. One pointer determines the iteration index, while the others determine the indexes of the register variables within each iteration.
US 2003/0123656 A1 discloses two scalar multiplication algorithms of the double-and-add-always type in which the point addition and doubling can be performed simultaneously at the expense of introducing some auxiliary variables. In addition, a number of techniques for the point addition and doubling are also proposed. The points are represented in projective coordinates, and the point addition and point doubling can be performed by using only the x and z coordinates, whereas the y coordinate can be recovered at the end by an appropriate algorithm without the inversion operation.
U.S. Pat. No. 6,212,277 B1 describes a technique for transforming an original elliptic curve over a prime field into an isomorphic curve for which the parameter a is much smaller, if possible equal to −3 mod p, so that the computations, in the Jacobian coordinates, can be somewhat simplified. The Applicant observes that resistance to side-channel attacks is not discussed.
US 2003/0142820 A1 deals with the elliptic curves given in the so-called Montgomery form, By2=x3+Ax2+x, which enables a somewhat faster scalar multiplication by using the Montgomery ladder algorithm. The points are represented in affine or projective coordinates and only the x (or x and z) coordinates are being computed. The document describes several improvements and/or modifications to these algorithms including an algorithm for recovering the y coordinate at the end of computations.
Yet another known method is to randomize the scalar multiplication algorithm by randomizing the elliptic curve in question, the base point, the coordinates, and/or the secret scalar itself, without changing the final result. This also helps counteracting the DPA attack, in addition to the timing attack and SPA attack.
In particular, it is suggested by P. Kocher, in “Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems,” Advances in Cryptology—Crypto '96, Lecture Notes in Computer Science, vol. 1109, pp. 104-113, 1996, to randomize the scalar by adding to it a random integer multiple of the base point order, n, in view of kP=kP+rnP=(k+rn)P. More precisely, this was suggested by using the multiplicative instead of additive terminology for a group operation, in which the exponentiation is an analog of the scalar multiplication.
J.-S. Coron suggested in “Resistance against differential power analysis for elliptic curve cryptosystems,” Cryptographic Hardware and Embedded Systems—CHES '99, Lecture Notes in Computer Science, vol. 1717, pp. 292-302, 1999, that a 20-bit random number r may be sufficient, but it was later shown by P.-A. Fouque and F. Valette, in “The doubling attack—Why upwards is better than downwards,” Cryptographic Hardware and Embedded Systems—CHES 2003, Lecture Notes in Computer Science, vol. 2779, pp. 269-280, 2003, that under some conditions this is not sufficiently secure, especially if the bit-size of r is relatively small and if one can distinguish the point addition from the point doubling.
Another technique for randomizing the scalar consists in splitting the scalar in two random parts by using the integer addition modulo n, according to k=k1+k2 mod n, and then to compute kP=k1P+k2P. An example of such a technique combined with the representation of points in the Jacobian coordinates is proposed in EP 1,217,783 A1.